/*************************************************************************
 * File Name:    Single_Number_II.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Mon 28 Oct 2013 10:17:17 PM CST
 * 
 * Description:  
 |
 |-------------------------------------------------------------------------
 | Single Number II
 |
 | Given an array of integers, every element appears three times except for one.
 | Find that single one.
 |
 | Note:
 | Your algorithm should have a linear runtime complexity. Could you implement
 | it without using extra memory?
 |-------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

class Solution {
public:
    int singleNumber(int A[], int n) {
        int cnt, ans;
        
        ans = 0;
        for (int i = 0; i < sizeof(int)*8; ++i) {
            cnt = 0;
            for (int j = 0; j < n; ++j) {
                if (A[j] & (1 << i)) ++cnt;
            }
            if (cnt % 3) ans |= 1 << i;
        }
        return ans;
    }
};

